import java.util.Stack;

public class Sort {
    /**
     * 使用static 静态方法 直接通过类名调用
     * 直接插入排序
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        //要求数组不为空
        for (int i = 1; i < array.length; i++) {
            //将 i 下标的值放入 tmp 中
            int tmp = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                //j下标的值和i下标的值进行比较
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
//                    array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 希尔排序
     * 不稳定排序
     */
    public static void shellSort(int[] array) {
        //首先要求出数组的长度
        int gap = array.length;
        //如何分组呢?
        //每次按照 数组的长度除以2进行分组
        while (gap > 1) {
            gap /= 2;
            //调用一个方法，对已经分好的组进行 直接插入排序
            shell(array, gap);
        }
    }

    private static void shell(int[] array, int gap) {
        //按照10个数据元素，分成2组来进行直接插入排序
        //每组有5的元素
        for (int i = gap; i < array.length; i++) {
            //定义一个临时变量存储 将要排序的元素
            int tmp = array[i];
            int j = 0;
            for (j = i - gap; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                    array[j] = tmp;
                } else {
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    /**
     * 选择排序
     * 不稳定排序
     *
     * @param array
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //用一个临时变量存储 最小值下标的值
            //首先默认 0 下标对应的值是最小值
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
                //接下来进行交换
                Sort.swap(array, i, minIndex);
            }

        }
    }

    /**
     * 交换方法
     *
     * @param array 数组
     * @param i
     * @param j     最小元素的下标
     */
    private static void swap(int[] array, int i, int j) {
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }

    public static void selectSort2(int[] array) {
        int left = 0;
        int right = array.length - 1;
        //判断条件是 left 与 right 相遇
        while (left < right) {
            //要定义 i
            int minIndex = left, maxIndex = left;
            for (int i = left + 1; i < right; i++) {
                if (array[i] < array[minIndex]) {
                    minIndex = i;
                } else if (array[i] > array[maxIndex]) {
                    maxIndex = i;
                }
            }


            //进行交换
            swap(array, minIndex, left);
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            swap(array, maxIndex, right);

            left++;
            right--;
        }
    }


    public static void quickSort(int[] array) {
        //首先要对待排序的元素进行划分
        //找到一个点，使左边比这个点小，右边比这个点大
        //可以以最左边或者最右边的元素作为基准
        //调用下面的方法进行划分
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        if ((end - start + 1) <= 19) {
            insertSort2(array, start, end);
        }

        //找基准之前，先对三数取中
        int index = middleNum(array, start, end);
        //找到中间元素下标之后
        //进行交换
        //把中间大的下标和第一个数字交换

        swap(array, index, start);

        //找到划分之后 基准元素的下标
        int pivot = partition(array, start, end);
        //以基准元素为点，又分左右两边
        //类似与二叉树的前序遍历
        quick(array, start, pivot - 1);//左边
        quick(array, pivot + 1, end);//右边
    }

    public static void insertSort2(int[] array, int start, int end) {
        //要求数组不为空
        for (int i = start + 1; i <= end; i++) {
            //将 i 下标的值放入 tmp 中
            int tmp = array[i];
            int j = i - 1;
            for (; j >= start; j--) {
                //j下标的值和i下标的值进行比较
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
//                    array[j + 1] = tmp;
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    private static int middleNum(int[] array, int left, int right) {
        //中间位置的下标
        int mid = left + ((right - left) >> 1);
        //怎么拿到这个下标对应的中间数字呢

        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            } else if (array[right] < array[mid]) {
                return right;
            } else {
                return mid;
            }
        } else {
            if (array[right] > array[mid]) {
                return right;
            } else if (array[mid] > array[left]) {
                return left;
            } else {
                return mid;
            }
        }
    }

    /**
     * Hoare法
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partitionHoare(int[] array, int left, int right) {
        //这里以最左边的元素为基准元素
        int tmp = array[left];
        //要先记录下来 left 的值，因为在下面操作过程中，left 的值会变
        int i = left;
        while (left < right) {

            while (left < right && array[right] >= tmp) {
                right--;
            }

            while (left < right && array[left] <= tmp) {
                left++;
            }

            //进行交换
            swap(array, left, right);
        }
        //将基准元素交换到中间
        swap(array, i, left);
        //返回此时基准元素的下标
        return left;
    }


    /**
     * 挖坑法
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    public static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {

            while (left < right && array[right] >= tmp) {
                right--;
            }
            if (left >= right) {
                break;
            }
            array[left] = array[right];

            while (left < right && array[left] <= tmp) {
                left++;
            }
            if (left >= right) {
                break;
            }
            array[right] = array[left];
        }

        array[left] = tmp;
        return left;
    }

    /**
     * 前后指针法
     */
    private static int partition2(int[] array, int left, int right) {
        int prev = left;
        int cur = left + 1;
        while (cur <= right) {
            if (array[cur] < array[left] && array[++prev] != array[cur]) {
                swap(array, cur, prev);
            }
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }

    private static int partition3(int[] array, int left, int right) {
        int d = left + 1;
        int pivot = array[left];
        for (int i = left + 1; i <= right; i++) {
            if (array[i] < pivot) {
                swap(array, i, d);
                d++;
            }
        }
        swap(array, d - 1, left);

        return d - 1;
    }


    /**
     * 快排非递归
     */
    public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array, left, right);


        if (pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot - 1);
        }

        if (pivot + 1 < right) {
            stack.push(right);
            stack.push(pivot + 1);
        }

        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array, left, right);


            if (pivot - 1 > left) {
                stack.push(left);
                stack.push(pivot - 1);
            }

            if (pivot + 1 < right) {
                stack.push(right);
                stack.push(pivot + 1);
            }
        }
    }

    /**
     * 归并排序
     *
     * @param array
     */
    public static void mergeSort(int[] array) {
        //首先要进行分解
        mergeFunc(array, 0, array.length - 1);
    }

    private static void mergeFunc(int[] array, int left, int right) {
        //递归结束时的判断条件
        if (left >= right) {
            //需要考虑什么时候 left > right
            return;
        }

        //找到中间点
        int mid = left + ((right - left) >> 1);
        //分界左边
        mergeFunc(array, left, mid);
        //分解右边
        mergeFunc(array, mid + 1, right);

        //进行合并
        //封装成一个方法
        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        //定义四个变量进行理解
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int k = 0;
        //申请一个额外的数组空间
        int[] tmpArray = new int[right - left + 1];
        //首先要保证两个原本的两段内容不为空，才能持续比较

        while (s1 <= e1 && s2 <= e2) {
            if (array[s1] >= array[s2]) {
                tmpArray[k++] = array[s2++];
            } else {
                tmpArray[k++] = array[s1++];
            }
        }

        //看哪个部分还有数据，拷贝到临时数组
        while (s1 <= e1) {
            tmpArray[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmpArray[k++] = array[s2++];
        }


        //再次拷贝到原数组
        for (int i = 0; i < k; i++) {
            array[i + left] = tmpArray[i];
        }
    }


    /**
     * 归并排序非递归
     *
     * @param array
     */
    public static void mergeSortNor(int[] array) {
        //首先定义每组排序的个数
        int gap = 1;
        while (gap < array.length) {
            //当gap = array.length时，说明这组数据有序
            for (int i = 0; i < array.length - 1; i = i + 2 * gap) {
                int left = i;
                int mid = left + gap - 1;
                //判断 mid  是否越界
                if (mid >= array.length) {
                    //重新赋值
                    mid = array.length - 1;
                }
                int right = mid + gap;
                //判断 right  是否越界
                if (right >= array.length) {
                    //重新赋值
                    right = array.length - 1;
                }
                //进行归并
                merge(array, left, mid, right);

            }
            //个数每次多2
            gap *= 2;
        }
    }

    public static void countSort(int[] array) {
        //首先要求该数组的最值
        //先假设
        int min = array[0];
        int max = array[0];

        for (int i = 0; i < array.length; i++) {
            if (min > array[i]) {
                min = array[i];
            }
            if (max < array[i]) {
                max = array[i];
            }
        }

        //创建一个计数数组
        int[] countArray = new int[max - min + 1];
        for (int i = 0; i < countArray.length; i++) {
            int index = array[i] - min;
            countArray[index]++;
        }

        //遍历计数数组
        //定义一个 k 记录array数组的下标
        int k = 0;
        for (int i = 0; i < countArray.length; i++) {
            while (countArray[i] != 0) {
                array[k] = i + min;
                k++;
                countArray[i]--;
            }
        }
    }
}







